I. Field of the Invention
The present invention relates to encryption. More particularly, the present invention relates to a method and apparatus for re-synchronizing encryption stream ciphers.
II. Background
Encryption is a process whereby a random process manipulates data such that the data is made unintelligible by all but the intended recipient. One method of encryption for digitized data is through the use of stream ciphers, which are generated by secret keys. A widely used secret key system is the Data Encryption Standard (DES) which employs a 56 bit key and 8 non-key parity bits. DES was published as a U.S. Federal Information Processing Standard in 1977. In an encryption scheme using a stream cipher, data and a stream of pseudo-random bits (or encryption bit stream) are combined, usually with the exclusive-or (XOR) operation. Many of the techniques used for generating the stream of pseudo-random numbers are based on linear feedback shift registers over a Galois finite field. The register is updated by shifting a new bit into the register, shifting the other bits over by one bit position, and calculating a new output bit. Decryption is simply the process of generating the same encryption bit stream and removing the encryption bit stream with the corresponding operation from the encrypted data. If the XOR operation was performed at the encryption side, the same XOR operation is also performed at the decryption side. For a secured encryption, the encryption bit stream must be computationally difficult to predict.
An exemplary application that utilizes stream ciphers is wireless telephony. An exemplary wireless telephony communication system is a code division multiple access (CDMA) system. The operation of a CDMA system is disclosed in U.S. Pat. No. 4,901,307, entitled “SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS,” assigned to the assignee of the present invention, and incorporated by reference herein. The CDMA system is further disclosed in U.S. Pat. No. 5,103,459, entitled SYSTEM AND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM, assigned to the assignee of the present invention, and incorporated by reference herein. Another CDMA system includes the GLOBALSTAR communication system for worldwide communication utilizing low earth orbiting satellites. Other wireless telephony systems include time division multiple access (TDMA) systems and frequency division multiple access (FDMA) systems. The CDMA systems can be designed to conform to the “TIA/EIA/IS-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System,” hereinafter referred to as the IS-95 standard. Similarly, the TDMA systems can be designed to conform to the TIA/EIA/IS-54 (TDMA) standard or to the European Global System for Mobile Communication (GSM) standard.
Encryption of digitized voice data in wireless telephony has been hampered by the lack of computational power in the remote station. This has led to weak encryption processes such as the Voice Privacy Mask used in the TDMA standard or to hardware generated stream ciphers such as the A5 cipher used in the GSM standard. The disadvantages of hardware-based stream ciphers are the additional manufacturing cost of the hardware and the longer time and larger cost involved in the event the encryption process needs to be changed. Since many mobile stations in wireless telephony systems and digital telephones comprise a microprocessor and memory, a stream cipher that is fast and uses little memory is well suited for these applications.
However, a problem arises in the use of stream ciphers in a wireless telephone system. A mobile station can travel from the range of a first base station to a second base station throughout the wireless telephone system. While the mobile station is travelling within the range of the system, the mobile station communicates with the base station from which the mobile station receives the strongest signal. It should be noted that a mobile station can detect the broadcasts of multiple base stations, not just the two base stations that are used herein for illustrative purposes. In most instances, the strength of a transmission signal is directly proportional to the distance between the mobile station and the base station. As the mobile station enters the range of a second base station, the mobile station begins communications with the second base station while concurrently maintaining communications with the first base station. The process in which the mobile station establishes communications with the second base station while ending communications with the first base station is called a “soft handoff,” and is described in U.S. Pat. No. 5,267,261, entitled “MOBILE STATION ASSISTED SOFT HANDOFF IN A CDMA CELLULAR COMMUNICATIONS SYTEM,” which is assigned to the assignee of the present invention, and incorporated by reference herein. If the mobile station is in the midst of a secure, encrypted data exchange with the first base station during handoff, it is necessary to re-synchronize the stream cipher so that the second base station and the mobile station can communicate securely without an interruption in the handoff process.
In order to achieve this goal, the second base station must be able to encrypt and decrypt in the same manner as the first base station. Hence, the second base station must have the state information or the synchronization parameters of the first base station. One simple method of re-synchronizing the stream cipher at the second base station is to pass information about the state of the encryption process from the first base station to the second base station through the wireless telephone system. However, the process of passing state information from one base station to another is problematic. If there is no mechanism for passing state information in a secure manner, the state information can be intercepted by unintended recipients and can then be used to compromise the security of the encrypted transmissions between the mobile station and the second base station.
Another simple method of re-synchronizing the stream cipher is to have both the mobile station and the second base station restart the entire encryption process from the same initial state as used by the mobile station and the first base station. However, this method results in a reused stream cipher, which is insecure. Thus, there is a need for a method that will provide secure resynchronization of a stream cipher while a mobile station is travelling within the range of a first base station to a second base station.